import java.util.LinkedList;
import java.util.Stack;

/**
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "(()"
 * 输出: 2
 * 解释: 最长有效括号子串为 "()"
 * 示例 2:
 * <p>
 * 输入: ")()())"
 * 输出: 4
 * 解释: 最长有效括号子串为 "()()"
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())"));
    }

    /**
     * 动态规划
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        int res = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 如果上一个是(，满足消除，则在上一个的集成上加2
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 如果上一个记录的待匹配是(，满足消除，则在上一个的集成上加2
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }

    /**
     * 使用链表
     *
     * @return
     */
    public static int longestValidParenthesesByLinkedList(String s) {
        // 用链表记录
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.push(-1);
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '*') {
                continue;
            }
            if (s.charAt(i) == ')') {
                // 出链表
                linkedList.pop();
                if (linkedList.isEmpty()) {
                    linkedList.push(i);
                } else {
                    // 求最值
                    max = Math.max(max, i - linkedList.peek());
                }
            } else {
                // 入链表
                linkedList.push(i);
            }
        }
        return max;
    }

    /**
     * 针对longestValidParentheses1进行了优化，代码好看了，性能没什么提升
     *
     * @param s
     * @return
     */
    public static int longestValidParentheses2(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        stack.push(0);

        for (int i = 1; i < s.length(); i++) {
            if (stack.size() > 1 && (s.charAt(stack.peek()) == '(' && s.charAt(i) == ')')) {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
        int pre = s.length(), tmp;
        do {
            tmp = stack.pop();
            max = Math.max(pre - tmp, max);
            pre = tmp;
        } while (!stack.isEmpty());
        return max - 1;
    }

    /**
     * 把字符和位置封成对象放到栈
     * 先消去
     * 然后再遍历栈，获取两个节点的最大差值
     *
     * @param s
     * @return
     */
    public static int longestValidParentheses1(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        // 使用堆栈，判断堆栈最大消除长度
        Stack<CharPosition> stack = new Stack<>();
        char c;
        for (int i = 0; i < s.length(); i++) {
            c = s.charAt(i);
            if (stack.isEmpty()) {
                stack.push(new CharPosition(c, i));
            } else {
                if (stack.peek().getChar() == '(' && c == ')') {
                    stack.pop();
                } else {
                    stack.push(new CharPosition(c, i));
                }
            }
        }
        // 遍历堆栈算出最大值
        if (stack.isEmpty()) {
            return s.length();
        }
        int max = 0, pre = s.length(), tmp;
        do {
            tmp = stack.pop().position;
            if (pre - tmp > max) {
                max = pre - tmp;
            }
            pre = tmp;
            if (stack.isEmpty()) {
                if (tmp > max) {
                    max = tmp + 1;
                }
            }
        } while (!stack.isEmpty());
        return max - 1;
    }

}

class CharPosition {
    char c;
    int position;

    CharPosition(char c, int position) {
        this.c = c;
        this.position = position;
    }

    char getChar() {
        return c;
    }

    int getPosition() {
        return position;
    }
}